package com.xj.util.tree.bplus;

import java.util.Random;

/**
 * http://blog.csdn.net/hbhhww/article/details/8206846
 * http://kevindude.iteye.com/blog/846726
 * http://hedengcheng.com/?p=525
 *(1) 每个节点最多可以有m个元素；
 *(2) 除了根节点外，每个节点最少有 (m/2) 个元素；
 *(3) 如果根节点不是叶节点，那么它最少有2个孩子节点；
 *(4) 所有的叶子节点都在同一层；
 *(5) 一个有k个孩子节点的非叶子节点有 (k-1) 个元素，按升序排列；
 *(6) 某个元素的左子树中的元素都比它小，右子树的元素都大于或等于它；
 *(7) 非叶子节点只存放关键字和指向下一个孩子节点的索引，记录只存放在叶子节点中；
 *(8) 相邻的叶子节点之间用指针相连。
 * User: bjxiajun
 * Date: 13-11-6
 * Time: 下午1:13
 */
public class BplusTree implements B {
    protected Node root;
    protected int order;
    protected Node head;

    public BplusTree(int order) {
        if (order < 3) {
            System.out.print("order must be greater than 2");
            throw new RuntimeException("order < 3");
        }
        this.order = order;
        root = new Node(true, true,order);
        head = root;
    }

    @Override
    public Object get(Comparable key) {
        return root.get(key);
    }

    @Override
    public void remove(Comparable key) {
        root.remove(key, this);
    }

    @Override
    public void insertOrUpdate(Comparable key, Object value) {
        root.insertOrUpdate(key, value, this);
    }

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }

    public Node getHead() {
        return head;
    }

    public void setHead(Node head) {
        this.head = head;
    }

    public int getOrder() {
        return order;
    }

    public void setOrder(int order) {
        this.order = order;
    }
    public static void list(Node root) {
        if (root.isLeaf()) {
            for (int i = 0; i < root.getEntries().size(); i++) {
                System.out.print(root.getEntries().get(i).getKey() + " ");
            }
        } else {
            for (int i = 0; i < root.getChildren().size(); i++) {
                list(root.getChildren().get(i));
            }
        }
    }
    public static void main(String[] args) {
        BplusTree tree = new BplusTree(32);
        Random random = new Random();
        long start = System.currentTimeMillis();
        for (int i = 0; i < 5000000; i++) {
            //int randomNumber = random.nextInt(5000000);
            tree.insertOrUpdate(i, i);
        }
        tree.insertOrUpdate(48,88);
        System.out.println("插入耗时: " + (System.currentTimeMillis() - start) + " ms");
    }
}
